'''
	This class represent an Binary Search Tree BST.
	
	Author: Samuel T. C. Santos
	Data  : 2014/04/14
	
'''

from node import Node

class BST :
	'''
	Initialization of the BST with node
	parent=Node(), left=Node(), right=Node() and data=None.
	'''
	def __init__(self):
		self.root = Node(None)
		self.root.parent = Node(None)

		
	'''
	 The method return the root of the BST.
	'''
	def getRoot(self):
		return self.root
		
	'''
	 This method return if the BST is empty, has no element!
	'''
	def isEmpty(self):
		return self.root.isEmpty()
		
	'''
	 The method return the height of the BST.
	'''
	def height(self):
		return self.heightNode(self.getRoot())
		
	def heightNode(self, node):
		leftHeight = 0
		rightHeight = 0
		
		TREE_EMPTY = -1
		
		if node.isEmpty():
			return TREE_EMPTY
		
		if not node.getLeft().isEmpty():
			leftHeight += 1 + self.heightNode(node.getLeft())
		
		if not node.getRight().isEmpty():
			rightHeight += 1 + self.heightNode(node.getRight())
		
		return max (leftHeight, rightHeight)
		
	'''
	 The method search find an value in the BST.
	'''
	def search(self, element):
		if self.isEmpty():
			return Node(None)
		else:
			return self.searchNode(element, self.getRoot())
		
		
	def searchNode(self, element, node):
		if (node.isEmpty()):
			return Node(None)
		else:
			if element == node.getData():
				return node
			else:
				if element < node.getData():
					return self.searchNode(element, node.getLeft())
				else:
					return self.searchNode(element, node.getRight())
		
	'''
	 This method insert an value in the BST.
	'''
	def insert(self, element):
		if (self.root.isEmpty()):
			self.root.setData(element)
			self.root.setLeft(Node(None))
			self.root.setRight(Node(None))
			self.root.getLeft().setParent(self.root)
			self.root.getRight().setParent(self.root)
		else:
			root = self.getRoot()
			self.insertNode(element,root)
	
	def insertNode(self, element, node):
		if element < node.getData():
			if node.getLeft().isEmpty():
				node.getLeft().setParent(node)
				node.getLeft().setData(element)
				node.getLeft().setLeft(Node(None))
				node.getLeft().setRight(Node(None))
			else:
				self.insertNode(element, node.getLeft())
		else:
			if node.getRight().isEmpty():
				node.getRight().setParent(node)
				node.getRight().setData(element)
				node.getRight().setLeft(Node(None))
				node.getRight().setRight(Node(None))
			else:
				self.insertNode(element, node.getRight())
		
		
	'''
	 This method remove an element in the BST.
	'''
	def remove(self, element):
		node = self.search(element)

		if not node.isEmpty():
			self.removeNode(node)
	
	def removeNode(self, node):
		if node.getLeft().isEmpty() and node.getRight().isEmpty():
			node.setData(None)
			node.setLeft(Node(None))
			node.setRight(Node(None))
		elif node.hasOneChild():
			if not node.equals(self.getRoot()):
			
				if node.isLeftChild():
					if not node.getLeft().isEmpty():
						node.getParent().setLeft(node.getLeft())
					else:
						node.getParent().setLeft(node.getRight())
				else:
					if not node.getLeft().isEmpty():
						node.getParent().setRight(node.getLeft())
					else:
						node.getParent().setRight(node.getRight())
			else:
				if not node.getRight().isEmpty():
					self.root = node.getRight()
				else:
					self.root = node.getLeft()

				self.root.setParent(Node(None))
		else:
			successor = self.successorNode(node)
			node.setData(successor.getData())
			self.removeNode(successor)


	'''
	 This method return the pre order walk.
	 ROOT-LEFT-RIGHT
	'''
	def preOrder(self):
		pre = []
		self.preOrderTreeWalk(pre, self.getRoot())
		return pre
		
	def preOrderTreeWalk(self, pre, node):
		if not node == None:
			if (not node.isEmpty()):
				pre.append(node.getData())
				
			self.preOrderTreeWalk(pre, node.getLeft())
			self.preOrderTreeWalk(pre, node.getRight())		
	
	'''
	 This method return the order walk.
	 LEFT-ROOT-RIGHT
	'''
	def order(self):
		order = []
		self.inOrderTreeWalk(order, self.getRoot())
		return order
		
	def inOrderTreeWalk(self, order, node):
	
		if not node == None:
			self.inOrderTreeWalk(order, node.getLeft())
			
			if (not node.isEmpty()):
				order.append(node.getData())
				
			self.inOrderTreeWalk(order, node.getRight())
		
	
	'''
	 This method return the post order walk.
	 LEFT-RIGHT-ROOT
	'''
	def postOrder(self):
		post = []
		self.postOrderTreeWalk(post, self.getRoot())
		return post
	
	
	def postOrderTreeWalk(self, post, node):
		
		if not node == None:
			
			self.postOrderTreeWalk(post, node.getLeft())
			self.postOrderTreeWalk(post, node.getRight())
			
			if (not node.isEmpty()):
				post.append(node.getData())
	
	'''
	 This method return the totol of keys
	 inserted into the BST.
	'''
	def size(self):
		return self.sizeNode(self.getRoot())
		
		
	def sizeNode(self, node):
		if node.isEmpty():
			return 0
		else:
			return 1 + self.sizeNode(node.getLeft()) + self.sizeNode(node.getRight())
	'''
	Minimum return the minimum value stored into
	the tree.
	'''
	def minimum(self):
		return self.minimumNode(self.getRoot())
	
	def minimumNode(self, node):
		current = node
		min = Node(None)
		while not current.isEmpty():
			min = current
			current = current.getLeft()
		
		return min
	
	'''
	Maximum return the maximum value stored into the tree.
	'''
	def maximum(self):
		return self.maximumNode(self.getRoot())
	
	def maximumNode(self, node):
		current = node
		max = Node(None)
		while not current.isEmpty():
			max = current
			current = current.getRight()
		
		return max
	
	'''
	 This method return the predecessor of the node
	 the predecessor is the greater value, less than
	 the value informed.
	'''
	def predecessor(self):
		if self.isEmpty():
			return Node(None)
		else:
			node = self.search(element)
			
			if not node.getData() == None:
				return self.successorNode(node)
			else:
				return Node(None)
		
	def predecessorNode(self, node):
		if not node.getLeft().isEmpty():
			return maximumNode(node.getLeft())
		
		parent = node.getParent()
		
		while not parent.isEmpty() and node.equals(parent.getLeft()):
			node = parent
			parent = parent.getParent()
			
		return parent
	
	'''
	 This method return the successor of the 
	 an value into the bst, the successor
	 is the smallest value greater than the
	 value informed.
	'''
	def successor(self, element):
		if self.isEmpty():
			return Node(None)
		else:
			node = self.search(element)
			
			if not node.getData() == None:
				return self.successorNode(node)
			else:
				return Node(None)
			
	'''
	 this method is an auxiliary method for 
	 find the successor.
	'''
	def successorNode(self, node):
		if not node.getRight().isEmpty():
			return self.minimumNode(node.getRight())
		else:
			parent = node.getParent()
			
			while not parent.isEmpty() and node.equals(parent.getRight()):
				node = parent
				parent = parent.getParent()
	
			return parent

